package com.xiaoyu.dp;

/**
 * @program: DS_and_A
 * @description:  买卖股票的最佳时机2
 *
 * 给定一个数组 prices ，其中prices[i] 是一支给定股票第 i 天的价格。
 *
 * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
 *
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 *
 * 示例 1:
 *
 * 输入: prices = [7,1,5,3,6,4]
 * 输出: 7
 * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
 *     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
 *
 * @author: YuWenYi
 * @create: 2021-05-23 13:26
 **/
public class MaxProfit2_122 {
    /*
    * 怎么分段?
        当后一个数字比当前数字小的时候,就分一段
        例如7,1,5,3,6,4,7,8
        理论分段之后: [7] [1,5] [3,6] [4,7,8]
        然后计算每一段的最大利益:
        0+4+3+4 = 11 即为所求答案
    * */
    //自己的思路,分段DP
    public int maxProfit1(int[] prices) {
        int minPrice = prices[0];
        int profit = 0;
        int sumOfProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i-1] > prices[i]){
                minPrice = prices[i];
            }else {
                profit = Math.max(profit, prices[i] - minPrice);
                //当i是最后一个数字,或者i的后一个数字大于当前数字的时候,就计算一次利益!
           /*
                两种情况:
                假设prices为7,1,5,3,6,7,即最后一段3,6,7后面无比7小的数字的时候,而这段也需要加入总利益中,
                所以就需要i == prices.length-1来进行判断!

                而7,1,5,3,6,7,4,即最后一段3,6,7后面还跟着唯一的一个比7小的数字,
                就需要使用prices[i+1] < prices[i]来判断,而且这段的含义是分段计算最大值,然后加入总和中

                i < prices.length-1是为了防止数组越界!
                */
                if ((i < prices.length-1 && prices[i+1] < prices[i]) || i == prices.length-1){
                    //获取一段的利益后,将其保存起来,然后将profit置0重新去计算下一段的利益
                    sumOfProfit += profit;
                    profit = 0;
                }
            }
        }
        return sumOfProfit;
    }

    //解法二:贪心算法  -->  只要有利可图,立刻将股票卖出,股价下跌就不买入
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            profit += Math.max(0,prices[i] - prices[i-1]);
        }
        return profit;
    }

    public static void main(String[] args) {
        MaxProfit2_122 profit122 = new MaxProfit2_122();
        int[] prices = {7,1,5,3,6,4};
        System.out.println(profit122.maxProfit(prices));
    }
}
